We provide the first black hole solutions with Lifshitz asymptotics found in string theory. These are expected to be dual to models enjoying anisotropic scale invariance with dynamical exponent z=2 at finite temperature. We employ a consistent truncation of type IIB supergravity to four dimensions with an arbitrary 5-dimensional Einstein manifold times a circle as internal geometry. New interesting features are found that significantly differ from previous results in phenomenological models. In particular, small black holes are shown to be thermodynamically unstable, analogously to the usual AdS-Schwarzschild black holes, and extremality is never reached. This signals a possible Hawking-Page like phase transition at low temperatures.